/* 

哈希问题
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。


示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
*/

// 我的答案
// var twoSum = function(nums, target) {
//     for (let i = 0; i < nums.length; i++) {//遍历两次数组
//         const e = nums[i];
//         for (let j = 0; j < nums.length; j++) {
//             const e2 = nums[j];
//             if( i!==j && e + e2 === target){//判断两个元素之和是否等于目标值,并且下标不能相等
//                 return [i, j];
//             }
//         }
//     }
// };

// let arr = [2, 7, 11, 8,7,15];
// let target = 14;
// console.log(twoSum(arr, target)); // [0, 1]


/*gpt的答案
使用 Map: 创建一个 Map 来存储数组元素及其对应的下标。
reduce 方法: 遍历数组，计算每个元素的补数（target - num），并检查补数是否已存在于 Map 中。
返回下标: 如果找到补数，则将补数的下标和当前元素的下标添加到结果数组中。
4. 输出结果: 最后返回找到的下标。
这个实现确保了时间复杂度为 O(n)，因为每个元素只被遍历一次。
*/
// var twoSum = function(nums, target) {
//     let map = new Map();
//     for (let i = 0; i < nums.length; i++) {
//         let diff = target - nums[i];
//         if (map.has(diff)) {
//             return [map.get(diff), i];
//         } else {
//             map.set(nums[i], i);
//         }
//     }
// }

// function twoSum(nums, target) {
//     const map = new Map();   
//     return nums.reduce((acc, num, index) => {
//         const complement = target - num;
//         if (map.has(complement)) {
//             acc.push(map.get(complement), index);
//         }
//         map.set(num, index);
//         return acc;
//     }, []);
// }



// 最快
/*数据结构: 使用 Map 来存储数组元素及其下标，提供 O(1) 的查找时间复杂度。
遍历数组: 使用 for 循环遍历 nums 数组的每个元素。
查找补数: 对于每个元素 nums[i]，计算其补数 target - nums[i]，并检查该补数是否已经存在于 Map 中。
4. 返回结果:
如果补数存在，使用 ids.get(target - nums[i]) 获取补数的下标，并与当前元素的下标 i 一起返回。
如果补数不存在，则将当前元素及其下标存入 Map 中，以便后续查找。
时间复杂度: 整个算法的时间复杂度为 O(n)，因为每个元素最多被访问两次（一次在查找补数时，一次在存入 Map 时）。
空间复杂度: 空间复杂度为 O(n)，因为在最坏情况下，所有元素都需要存储在 Map 中*/

var twoSum = function(nums, target) {
    let ids = new Map(); // 创建一个 Map 用于存储数组元素及其对应的下标
    for(let i = 0; i < nums.length; i++){ // 遍历数组
        if(ids.has(target - nums[i])){ // 检查当前元素的补数是否已存在于 Map 中
            return [ids.get(target - nums[i]), i]; // 如果存在，返回补数的下标和当前元素的下标
        }
        ids.set(nums[i], i); // 将当前元素及其下标存入 Map
    }
};

let arr = [2, 7, 11, 8,7,15];
console.log(`output->twoSum(arr,9)`,twoSum(arr,9))